An error-correcting code is a technique to reduce the effects of noise occurring during data transmission in the process of coding and decoding. Coding is a process of adding redundancy to data to be transmitted, and the coded data is called a codeword. A codeword sent into a communication channel is affected by noise, resulting in an error such as having some bits inverted when the codeword is received. Decoding is a process of restoring the original data from the error-ridden received word by using redundancy.
The LDPC code is the error-correcting code proposed in 1960s; however, it had not drawn attention until late 1990s, when a relation with the Turbo code was pointed out (For example, see Non-Patent Literature 1).
The LDPC code is characterized by having a sparse parity check matrix with a small number of small loops when represented by the Tanner graph, and, because of such characteristics, there is a high-performance decoding method with relatively high efficiency. The decoding method is called Message-Passing decoding (hereinafter abbreviated as MP decoding).
The MP decoding of LDPC codes is performed by iteratively updating reliability information of codeword bits by column processing corresponding to columns of the parity check matrix and row processing corresponding to rows of the same. The reliability information generated by the row processing is called external information. The sequence of the iterative update is arbitrary. Serial scheduling in which the external information which has been updated in the row processing is used in the subsequent row processing in the same iteration is also called layered scheduling, which is disclosed in Non-Patent Literatures 2 and 3, for example.
The received value and the reliability information are generally stored in the form of log-likelihood ratio (LLR). In typical implementation of the serial scheduling, a plurality of memories that store cumulative LLR that is received values or the sum of received values and external information, and a plurality of memories that store external information are included. The former is referred to as cumulative LLR memories, the latter is referred to as external information memories, and they are collectively referred to as LLR memories.
Although the speedup of a decoding process is achieved by parallel processing that concurrently performs row processing on a plurality of rows, an access method to the LLR memories and routing of data between the LLR memories and processors are raised as issues. A pseudo-cyclic LDPC code is known as the code class capable of addressing such issues with high efficiency.
FIG. 8 shows an example of a parity check matrix of the pseudo-cyclic LDPC code. As shown in FIG. 8, the parity check matrix is made up of square submatrices of the same size, and the submatrices correspond to matrices I(j,k) representing a cyclic permutation formed by shifting a zero matrix or a unit matrix. Note that FIG. 8 shows an example of a parity check matrix with a cyclic permutation size Z=5. Row and column components in units of the submatrices are respectively referred to as a row block and a column block. In the example of FIG. 8 with a cyclic permutation size Z=5, the parity check matrix is made up of row blocks 0, 1, 2 and 3 and column blocks 0, 1, 2, 3 and 4. Further, in the parity check matrix, one number in columns and rows are respectively called the column order and the row order.
In the pseudo-cyclic LDPC code, the columns or the rows in the same column block or the same row block have the same order. The submatrices which are not a zero matrix in a column block k (order d_k) are represented as I(0,k), I(1,k), . . . , I(d_k−1,k) sequentially from the top. I(j,k) can be represented using a shift value for each row of a unit matrix, and it is represented as s(j,k). For example, s(j,k)=0,1 represents that I(j,k) is a unit matrix, and each row of the unit matrix is shifted by one cycle to the right.
In the pseudo-cyclic LDPC code, processing can be performed efficiently by carrying out parallel processing in units of Z number of rows for the cyclic permutation size Z. The cumulative LLR and the external information are read and written in units of Z number of data in one column block as one record. FIG. 9 is a schematic diagram showing a cumulative LLR memory structure and a data storing method for the parity check matrix of FIG. 8.
In FIG. 9, “0 1 2 3 4” in one record means storing data corresponding to positions from 0 to 4 (in the case of Z=5) in each column block. In the parity check matrix of FIG. 8, the column blocks 0 and 1 and the column blocks 3 and 4 do not make simultaneous access to the cumulative LLR memory, and therefore they can be stored in the same cumulative LLR memory. Thus, in such a case, a decoding device can be configured using three independent cumulative LLR memories, i.e., a cumulative LLR memory 0 storing the column blocks 0 and 1, a cumulative LLR memory 1 storing the column block 2, and a cumulative LLR memory 2 storing the column blocks 3 and 4.
During reading from the cumulative LLR memory, data which has been read in units of records is cyclically permutated according to I(j,k) by barrel shift and transmitted to components for performing the column processing and the row processing. The cumulative LLR updated herein undergoes the cyclic permutation corresponding to the inverse permutation of I(j,k) and written to the cumulative LLR memory.
In an application of mobile communication and the like, a frame structure that enables flexible handling of a channel state, a transmission data size and the like is required, and an error-correcting code needs to have a variable code length. The pseudo-cyclic LDPC code can satisfy the need by making the cyclic permutation size Z variable.
However, when the cyclic permutation size Z is made variable, the overhead of a cyclic permutation means which accompanies parallel processing tends to increase according to the fineness of setting. The most straightforward way is to prepare cyclic permutation means corresponding to all possible cyclic permutation sizes Z and switch them depending on the value of the actual cyclic permutation size Z. However, this is extremely wasteful when there are many different cyclic permutation sizes Z.
When the cyclic permutation size Z is a multiple of a certain integer, it can be represented by the pseudo-cyclic LDPC code based on cyclic permutation with the size of the integer by replacing rows and columns. However, in this method also, when detailed setting of the cyclic permutation size Z is possible, it is represented as the pseudo-cyclic LDPC code with a small cyclic permutation size, and the degree of parallelism is not so large, failing to achieve speedup.
Implementation of a decoding device which is compatible with any shift size Z or cyclic permutation size Z in a process of a fixed degree of parallelism S (the number of data in a LLR record) is a desirable form of implementation of a decoding device intended for an application with a variable code length. In this case, in column processing/row processing components, it is enough to prepare S number of processors for the column processing 1 and the column processing 2, and is possible to operate them efficiently if S number of data is input each time. Under the condition that the cyclic permutation size Z is 2 S or more, an implementation example of this method is described in Patent Literature 1, i.e., WO2008/069231.
According to the technique of Patent Literature 1, a LLR memory for storing reliability information stores data in a cyclically magnified manner so that it is a multiple of the degree of parallelism S. FIG. 10 is a schematic diagram of a data storing method of a cumulative LLR memory in Patent Literature 1. As shown in FIG. 10, the final record is made up of data corresponding to indexes 12, 13, 14, 0, 1, 2 in the column block. The depth D of the LLR memory per column block is 3.
In practice, data is stored in units of column blocks in an alignment corresponding to the maximum value MaxZ of the cyclic permutation size Z. The row processing is also executed in a cyclically magnified manner. The cyclic permutation is implemented by a multistage cyclic permutation means that executes, for input in units of records with the size S or the degree of parallelism S, output with the size S conforming to I(j,k) by a shift and a selection switch from two adjacent records in multiple stages. During writing to the memory, the multistage cyclic permutation means with the size S, which is inverse permutation of I(j,k), is executed.
FIG. 11 is a block diagram showing a configuration of a decoding device according to related art, and it shows a configuration of a decoding device for serial scheduling in Patent Literature 1. In FIG. 11, a ROM 100 is a memory that stores the structure of the parity check matrix and information of I(j,k) in FIG. 8. Further, a cumulative LLR memory 101 is a memory that stores cumulative LLR that is received values or the sum of received values and external information in units of records each containing S number of data (in units of single reading/writing). Although FIG. 11 shows an image with two cumulative LLR memories 101, it is enough to prepare three cumulative LLR memories 101 as shown in FIG. 9 if a code has the parity check matrix of FIG. 8.
A memory input control 102 sorts the received values input to the decoding device out to the cumulative LLR memories according to the structure of the column block of the parity check matrix. A record generation means 103a performs processing of generating records each containing S number of data from the received values, which are the input data to the decoding device.
Multistage cyclic permutation means 106a and 106b execute cyclic permutation processing corresponding to I(j,k) and the inverse permutation of I(j,k), i.e., I(j,k)^{−1} (−s(j,k)mod Z in a shift value), respectively, for the cumulative LLR by input/output in units of records with the size S.
A column processing/row processing component 105 is a device for actually performing the MP decoding, and S number of column processing/row processing components 105 operate independently of one another. Although an external information memory is in the form of a constituent element of the column processing/row processing components 105 in FIG. 11, a configuration in which a column processing means is placed between the cumulative LLR memory 101 and the cyclic permutation processing may be adopted.
A hard decision means 107 makes decision of 0 or 1 on a decoding result from the cumulative LLR. Further, a decoding result memory 108 is a memory that stores a hard decision result of the hard decision means 107. An output sequence forming means 109a performs processing of forming an output bit sequence by eliminating a cyclically padded portion in the decoding result. A control means 110a adjusts parameters in accordance with the cyclic permutation size Z at the start of decoding, and, when processing a column block corresponding to I(j,k), generates addresses of the column processing/row processing components 105 and the cumulative LLR memory 101 according thereto.